學習資源

https://labuladong.online/algo/intro/complexity-basic/

學習記錄

今天是學習的第 1 天，主要學習了時間 / 空間複雜度：

• 時間 / 空間複雜度會使用 Big O 表示，它們都是預估值，常數項和低增長項都可以忽略，僅需保留最高增長項，一開始看到這邊其實不太懂，看了範例後才知道意思。

O(2n²+3n+1) 等同於 O(n²)
O(1000n+1000) 等同於 O(n)

• 演算法的時間複雜度和空間複雜度都是越小越好。
• 在分析演算法複雜度時，分析的是 「最壞情況」 下的複雜度，底下會有範例說明這件事。
• 時間複雜度用來衡量一個演算法的執行效率，空間複雜度用來衡量演算法的記憶體消耗。

這邊的 n 是指什麼？

這邊可以簡單理解為：

• 時間複雜度：大部分情況下就是看 for 迴圈的最大巢狀層數
• 空間複雜度：看演算法申請了多少空間來儲存資料

案例分析

範例一：時間複雜度 O(n)，空間複雜度 O(1)

var getSum = function(nums) {
    var sum = 0;
    for (var i = 0; i < nums.length; i++) {
        sum += nums[i];
    }
    return sum;
}

演算法包含了一個 for 循環遍歷 nums 陣列，所以時間複雜度是 O(n)，其中 n 代表 nums 陣列的長度。

演算法只使用了一個 sum 變數，這個 nums 是題目給的輸入，不算在演算法的空間複雜度裡面，所以空間複雜度是 O(1)。

範例二：時間複雜度 O(n)，空間複雜度 O(1)

var sum = function(n) {
    if (n % 10 !== 0) {
        return -1;
    }
    var sum = 0;
    for (var i = 0; i <= n; i++) {
        sum += i;
    }
    return sum;
}

當 n 是 10 的倍數時，演算法才會執行 for 循環，時間複雜度是 O(n)。其他情況下演算法會直接返回，時間複雜度是 O(1)。

但是上面有提到在分析演算法複雜度時，分析的是「最壞情況」的複雜度，所以這個演算法的時間複雜度是 O(n)，空間複雜度是 O(1)。

範例三：時間複雜度 O(n²)，空間複雜度 O(1)

var hasTargetSum = function(nums, target) {
    for (var i = 0; i < nums.length; i++) {
        for (var j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return true;
            }
        }
    }
    return false;
}

因為演算法嵌套了兩層 for 循環，所以時間複雜度是 O(n²)，其中 n 代表 nums 陣列的長度。

演算法只使用了 i, j 兩個變數，這是常數層級的空間消耗，所以空間複雜度是 O(1)，因為上面有提到常數項和低增長項都可以忽略。

學習總結

• 時間 / 空間複雜度會使用 Big O 表示
• 演算法分析的是 「最壞情況」 下的複雜度
• 時間複雜度用來衡量一個演算法的執行效率，空間複雜度用來衡量演算法的記憶體消耗。
• 一般情況下，時間複雜度看 for 迴圈的最大巢狀層數；空間複雜度看申請了多少空間來儲存資料